package 动态规划;

import java.util.HashSet;
import java.util.List;
import java.util.Set;

/*
    @author TTDB
    @create 2025/9/5
*/
public class wordBreak {
     public boolean wordBreak(String s, List<String> wordDict) {
         //完全背包问题，可以重复选取元素
         Set set = new HashSet<>(wordDict);
         int n = s.length();
         boolean[] f = new boolean[n + 1];
         f[0] = true;
         for(int i = 1; i <= n; i++){
             for(int j = 1; j <= i && !f[i]; j++){
                 String sub = s.substring(j - 1, i);
                 if(set.contains(sub)) f[i] = f[j-1];
             }
         }
         return f[n];
    }
}
